2403. Сильная связность

Назовём компонентой сильной связности в ориентированном графе такое множество вершин, что из любой вершины этого множества существует путь в любую другую вершину этого же множества, и не существует другого множества с аналогичными свойствами, которое бы включало в себя данное множество.

Дан ориентированный граф. Найдите количество различных компонент сильной связности в нём.

Вход. В первой строке заданы два целых числа n и m (1 ≤ n ≤ 10, 0 ≤ m ≤ 90) – количество вершин и рёбер в графе соответственно. Следующие m строк описывают рёбра графа: i-ая из этих строк содержит два числа u_i и v_i (1 ≤ u_i, v_i ≤ n) – номера начала и конца i-го ребра соответственно. Гарантируется, что граф не содержит петель и кратных рёбер.

Выход. Выведите одно число – количество компонент сильной связности данного графа.

Пример входа 1	Пример выхода 1
3 2 1 2 2 3	3

Пример входа 2	Пример выхода 2
5 4 3 1 1 2 2 3 4 5	3

РЕШЕНИЕ

графы – сильная связность

Анализ алгоритма

В ориентированном графе следует найти количество сильно связных компонент.

Пример

Графы, приведенные в примерах, имеют вид:

Каждый из графов содержит 3 сильно связные компоненты.

Реализация алгоритма

Входной граф храним в списке смежности g. Обратный граф храним в gr.

vector<vector<int> > g, gr;

vector<int> used, top;

Функция dfs1 реализует поиск в глубину на входном графе. В массив top заносим последовательность вершин, в которой поиск в глубину завершает их обработку.

void dfs1(int v)

{

used[v] = 1;

for (int to : g[v])

if (!used[to]) dfs1(to);

top.push_back(v);

}

Функция dfs2 реализует поиск в глубину на обратном графе. Все вершины, которые будут пройдены в результате рекурсивного вызова функции dfs2, принадлежат одной компоненте сильной связности.

void dfs2(int v)

{

used[v] = 1;

for (int to : gr[v])

if (!used[to]) dfs2(to);

}

Основная часть программы. Читаем входные данные. Строим обратный граф.

scanf("%d %d", &n, &m);

g.resize(n + 1);

gr.resize(n + 1);

for(i = 1; i <= m; i++)

{

scanf("%d %d", &a, &b);

g[a].push_back(b);

gr[b].push_back(a);

}

Запускаем поиск в глубину на входном графе. Последовательность, в которой завершается обработка вершин графа, сохраняется в массиве top.

used.resize(n+1);

for(i = 1; i <= n; i++)

if (!used[i]) dfs1(i);

Запускаем поиск в глубину на обратном графе. Вершины обратного графа следует рассматривать в порядке обхода массива top справа налево (с конца в начало). Для удобства дальнейшей обработки обернем массив top.

used.clear();

used.resize(n + 1);

reverse(top.begin(), top.end());

В переменной c подсчитываем количество сильно связных компонент.

c = 0;

Теперь двигаемся по массиву top слева направо и вызываем из каждой еще непосещенной вершины поиск в глубину dfs2.

for (int v : top)

if (!used[v])

{

dfs2(v);

c++;

}

Выводим количество компонент сильной связности графа.

printf("%d\n",c);

Java реализация

import java.util.*;

public class Main

{

static ArrayList<Integer>[] g, gr;

static boolean used[];

static Vector<Integer> top = new Vector<Integer>();

static void dfs1(int v)

{

used[v] = true;

for(int i = 0; i < g[v].size(); i++)

{

int to = g[v].get(i);

if (!used[to]) dfs1(to);

}

top.add(v);

}

static void dfs2(int v)

{

used[v] = true;

for(int i = 0; i < gr[v].size(); i++)

{

int to = gr[v].get(i);

if (!used[to]) dfs2(to);

}

@SuppressWarnings("unchecked")

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m = con.nextInt();

g = new ArrayList[n+1];

for(int i = 0; i <= n; i++)

g[i] = new ArrayList<Integer>();

gr = new ArrayList[n+1];

for(int i = 0; i <= n; i++)

gr[i] = new ArrayList<Integer>();

for (int i = 0; i < m; i++)

{

int a = con.nextInt();

int b = con.nextInt();

g[a].add(b);

gr[b].add(a);

}

used = new boolean[n+1];

for(int i = 1; i <= n; i++)

if (!used[i]) dfs1(i);

used = new boolean[n+1];

int c = 0;

for(int i = 1; i <= n; i++)

{

int v = top.get(n-i);

if (!used[v])

{

dfs2(v);

c++;

}

System.out.println(c);

con.close();

}

Python реализация

def dfs1(v):

global g, used, top

used[v] = True

for to in g[v]:

if not used[to]: dfs1(to)

top.append(v)

def dfs2(v):

global gr, used

used[v] = True

for to in gr[v]:

if not used[to]: dfs2(to)

Основная часть программы. Читаем входные данные. Строим обратный граф.

n, m = map(int, input().split())

g = [[] for _ in range(n + 1)]

gr = [[] for _ in range(n + 1)]

for _ in range(m):

a, b = map(int, input().split())

g[a].append(b)

gr[b].append(a)

used = [False] * (n + 1)

top = []

for i in range(1, n + 1):

if not used[i]: dfs1(i)

used = [False] * (n + 1)

top.reverse()

В переменной c подсчитываем количество сильно связных компонент.

c = 0

for v in top:

if not used[v]:

dfs2(v)

c += 1

Выводим количество компонент сильной связности графа.

print(c)